#pragma once

#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include "ToInt.h"
using namespace std;

template<class T>
struct HashNode
{
	T _data;
	HashNode<T>* _next;

	HashNode(const T& data)
		:_data(data)
		, _next(nullptr)
	{}
};

template<class K, class T, class KeyOfT, class ToInteger>
class HashTable;

template<class K, class T, class Ref, class Ptr, class KeyOfT, class ToInteger>
struct ht_iterator
{
	typedef HashNode<T> Node;
	typedef HashTable<K, T, KeyOfT, ToInteger> HT;
	typedef ht_iterator<K, T, Ref, Ptr, KeyOfT, ToInteger> Self;

	Node* _ptr;
	const HT* _ht;

	ht_iterator(Node* ptr, const HT* ht)
		:_ptr(ptr)
		, _ht(ht)
	{}

	Ref operator*()
	{
		return _ptr->_data;
	}

	Ptr operator->()
	{
		return &(_ptr->_data);
	}

	Self& operator++()
	{
		if (_ptr->_next)
		{
			_ptr = _ptr->_next;
		}
		else
		{
			size_t hashi = _toi(_kot(_ptr->_data)) % _ht->_tables.size();
			hashi++;
			while (hashi < _ht->_tables.size())
			{
				if (_ht->_tables[hashi])
				{
					_ptr = _ht->_tables[hashi];
					break;
				}
				hashi++;
			}
			if (hashi == _ht->_tables.size())
			{
				_ptr = nullptr;
			}
		}
		return *this;
	}

	bool operator!=(const Self& it)
	{
		return _ptr != it._ptr;
	}

	bool operator==(const Self& it)
	{
		return _ptr == it._ptr;
	}

	ToInteger _toi;
	KeyOfT _kot;
};

template<class K, class T, class KeyOfT, class ToInteger>
class HashTable
{
	typedef HashNode<T> Node;

	template<class K, class T, class Ref, class Ptr, class KeyOfT, class ToInteger>
	friend struct ht_iterator;
public:
	typedef ht_iterator<K, T, T&, T*, KeyOfT, ToInteger> Iterator;
	typedef ht_iterator<K, T, const T&, const T*, KeyOfT, ToInteger> ConstIterator;

	HashTable()
	{
		_tables.resize(__stl_next_prime(1), nullptr);
	}

	~HashTable()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			while (cur)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
			_tables[i] = nullptr;
		}
	}

	Iterator Begin()
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			if (cur) return Iterator(cur, this);
		}
		return End();
	}

	Iterator End()
	{
		return Iterator(nullptr, this);
	}

	ConstIterator Begin() const
	{
		for (size_t i = 0; i < _tables.size(); i++)
		{
			Node* cur = _tables[i];
			if (cur) return Iterator(cur, this);
		}
		return End();
	}

	ConstIterator End() const
	{
		return Iterator(nullptr, this);
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		Iterator it = Find(_kot(data));
		if (it != End())
		{
			return { it,false };
		}
		if (_n == _tables.size())
		{
			size_t newSize = __stl_next_prime(_tables.size() + 1);
			vector<Node*> newV(newSize, nullptr);
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;
					size_t hashi = _toi(_kot(cur->_data)) % newV.size();
					cur->_next = newV[hashi];
					newV[hashi] = cur;
					cur = next;
				}
				_tables[i] = nullptr;
			}
			_tables.swap(newV);
		}
		size_t hashi = _toi(_kot(data)) % _tables.size();
		Node* newnode = new Node(data);
		newnode->_next = _tables[hashi];
		_tables[hashi] = newnode;
		_n++;
		return { Iterator(newnode,this),true };
	}

	Iterator Find(const K& key)
	{
		size_t hashi = _toi(key) % _tables.size();
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (_kot(cur->_data) == key)
			{
				return Iterator(cur, this);
			}
			cur = cur->_next;
		}
		return Iterator(nullptr, this);
	}

	bool Erase(const K& key)
	{
		size_t hashi = _toi(key) % _tables.size();
		Node* prev = nullptr;
		Node* cur = _tables[hashi];
		while (cur)
		{
			if (_kot(cur->_data) == key)
			{
				if (prev == nullptr)
				{
					_tables[hashi] = cur->_next;
				}
				else
				{
					prev->_next = cur->_next;
				}
				delete cur;
				_n--;
				return true;
			}
			prev = cur;
			cur = cur->_next;
		}
		return false;
	}
private:
	inline size_t __stl_next_prime(size_t n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const size_t __stl_prime_list[__stl_num_primes] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const size_t* first = __stl_prime_list;
		const size_t* last = __stl_prime_list + __stl_num_primes;
		const size_t* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}

	vector<Node*> _tables;
	size_t _n = 0;
	ToInteger _toi;
	KeyOfT _kot;
};